package butines.core.game.lqdb;

import java.util.ArrayList;
import java.util.List;


public class SpatialDatabase {

	public class BinNode {
		private Integer head;
		private BinNode prev;
		private BinNode next;
		private float x, y;
		private Object object;
				
		private BinNode(Object object) {
			this.object = object;
		}

		private float distanceSq(float cx, float cy) {
			float a = x - cx;
			float b = y - cy;
			return a * a + b * b;
		}
		
		public String toString() {
			return (prev != null ? " < " : "") + object + (next != null ? " > " : "");
		}
		
	}
	
	private int divx, divy;
	private float originx, originy;
	private float sizex, sizey;
	private float width, height;
	private BinNode[] bins;
	private int count;
	
	public SpatialDatabase(float originx, float originy, float sizex, float sizey, int divx, int divy) {
		this.originx = originx;
		this.originy = originy;
		this.sizex = sizex;
		this.sizey = sizey;
		this.divx = divx;
		this.divy = divy;
		
		width = sizex / divx;
		height = sizex / divx;
		bins = new BinNode[divx * divy + 1];
	}
		
	public int getDivx() {
		return divx;
	}

	public int getDivy() {
		return divy;
	}

	public float getOriginx() {
		return originx;
	}

	public float getOriginy() {
		return originy;
	}

	public float getSizex() {
		return sizex;
	}

	public float getSizey() {
		return sizey;
	}
	
	public float getWidth() {
		return width;
	}

	public float getHeight() {
		return height;
	}
	
	public int length() {
		return bins.length;
	}
	
	public int count() {
		return count;
	}
	
	public int count(int head) {
		BinNode bin = bins[head];
		int count = 0;
		while (bin != null) {
			count++;
			bin = bin.next;
		}
		return count;
	}
	
	public Integer getHead(float x, float y) {
		/* if point outside super-brick, return the "other" bin */
		if (x < originx || y < originy || x >= originx + sizex || y >= originy + sizey) {
			return bins.length - 1;
		}
		/* if point inside super-brick, compute the bin coordinates */
		int ix = (int)(((x - originx) / sizex) * divx);
		int iy = (int)(((y - originy) / sizey) * divy);

		/* convert to linear bin number */
		int head = iy * divx + ix;

		/* return pointer to that bin */
		return head;
	}
	
	public BinNode getBin(int head) {
		return bins[head];
	}
	
	public BinNode getBin(float x, float y) {
		int head = getHead(x, y);
		return bins[head];
	}
	
	public BinNode getOther() {
		return bins[bins.length - 1];
	}
	
	public BinNode createBin(Object object) {
		return new BinNode(object);
	}
	
	public void add(BinNode bin, int head) {
		bin.head = head;
		if (bins[head] == null) {
			bin.prev = null;
			bin.next = null;
		} else {
			bin.prev = null;
			bin.next = bins[head];
			bins[head].prev = bin;
		}
		bins[head] = bin;
		count++;
	}
	
	public void remove(BinNode bin) {
		if (bin.head != null) {
			if (bins[bin.head] == bin) {
				bins[bin.head] = bin.next;
			}
			if (bin.prev != null) {
				bin.prev.next = bin.next;
			}
			if (bin.next != null) {
				bin.next.prev = bin.prev;
			}
			count--;
		}
		bin.prev = null;
		bin.next = null;
		bin.head = null;
	}
		
	public void update(BinNode bin, float newx, float newy) {
		Integer head = getHead(newx, newy);
		bin.x = newx;
		bin.y = newy;
		if (head != bin.head) {
			remove(bin);
			add(bin, head);
		}
	}
	
	
	
	private ArrayList<Object> foundObjects = new ArrayList<Object>();
	private QueryState queryState = new QueryState();
	
	public List<?> findObjects(float centerx, float centery, float radius) {	
		foundObjects.clear();
		queryState.init(centerx, centery, radius);
		if (queryState.isCompleteOutside()) {
			queryState.findObjectsOutsite();
		} else {
			if (queryState.isPartlyOutside()) {
				queryState.findObjectsOutsite();
			}		
			queryState.findObjectsInside();
		}
		return foundObjects;
	}
	
	public List<?> findAllObjects() {
		foundObjects.clear();
		for (BinNode bin: bins) {
			while (bin != null) {
				foundObjects.add(bin.object);
				bin = bin.next;
			}
		}
		return foundObjects;
	}
	
	public void removeAllObjects() {
		for (int i = 0; i < bins.length; i++) {
			BinNode bin = bins[i];
			while (bin != null) {
				BinNode next = bin.next;
				bin.prev = null;
				bin.next = null;
				bin.head = null;
				count--;
				bin = next;
			}
		}
	}
	
//	public void annotation(G2D g2d) {
//		float w = sizex/divx;
//		float h = sizey/divy;
//		g2d.setColor(Color.PINK);
//		for (float x = originx; x < sizex; x += w) {
//			for (float y = originy; y < sizey; y += h) {
//				g2d.drawRect(x, y, w-1, h-1);
//				int head = getHead(x, y);
//				g2d.setAlign(0, 0).print(x+w/2, y+h/2, "[{0}]", head);
//				BinNode bin = bins[head];
//				int i = 0;
//				while (bin != null) {
//					g2d.setAlign(0, 0).print(bin.x, bin.y, "({0})", i);
//					bin = bin.next;
//					i++;
//				}
//			}
//		}
//		
//	}
	
	
	
	private class QueryState {
		float centerx;
		float centery;
		float radius;
		float radiusSq;
		
		int minBinX;
		int minBinY;
		int maxBinX;
		int maxBinY;
		
		private QueryState() {
		}
		
		public void init(float centerx, float centery, float radius) {
			this.centerx = centerx;
			this.centery = centery;
			this.radius = radius;
			this.radiusSq = radius * radius;
		}
		
		boolean isCompleteOutside() {
			return (centerx + radius) < originx
				|| (centery + radius) < originy
				|| (centerx - radius) >= originx + sizex
				|| (centery - radius) >= originy + sizey;
		}
		
		boolean isPartlyOutside() {
			boolean partlyOutside = false;
			/* compute min and max bin coordinates for each dimension */
			minBinX = (int)((((centerx - radius) - originx) / sizex) * divx);
			minBinY = (int)((((centery - radius) - originy) / sizey) * divy);
			maxBinX = (int)((((centerx + radius) - originx) / sizex) * divx);
			maxBinY = (int)((((centery + radius) - originy) / sizey) * divy);
			/* clip bin coordinates */
			if (minBinX < 0) {
				partlyOutside = true;
				minBinX = 0;
			}
			if (minBinY < 0) {
				partlyOutside = true;
				minBinY = 0;
			}
			if (maxBinX >= divx) {
				partlyOutside = true;
				maxBinX = divx - 1;
			}
			if (maxBinY >= divy) {
				partlyOutside = true; 
				maxBinY = divy - 1; 
			}
			
			return partlyOutside;
		}
		
		boolean isMatch(BinNode bin) {
			return bin.distanceSq(centerx, centery) <= radiusSq;
		}
		
		void add(BinNode bin) {
			foundObjects.add(bin.object);
		}
		
		private void findObjectsInside() {
			for (int x = minBinX; x <= maxBinX; x++) {
				for (int y = minBinY; y <= maxBinY; y++) {
					BinNode bin = bins[y * divx + x];
					search(bin);
				}
			}
		}
		
		private void findObjectsOutsite() {
			search(getOther());
		}
		
		private void search(BinNode bin) {
			while (bin != null) {
				if (isMatch(bin)) {
					add(bin);
				}
				bin = bin.next;
			}
		}
		
	}
	
}
